Các đội trẻ Anh

Mặc dù sinh ra tại Nigeria, Moses đã chọn thi đấu cho đội trẻ U-16 của Anh và giành danh hiệu Victory Shield năm 2005. Năm 2007, anh cùng đội tuyển U-17 Anh tham dự Giải vô địch U-17 châu Âu tại Bỉ. Tại giải đấu này anh ghi được 3 bàn (cú đúp trong trận gặp U-17 Hà Lan[64] và bàn thắng duy nhất trong trận bán kết với U-17 Pháp[65]), giành được danh hiệu Chiếc giày Vàng và đội tuyển U-17 Anh đứng thứ hai giải đấu sau U-17 Tây Ban Nha. Cùng năm đó, anh tiếp tục cùng U-17 Anh tham dự Giải vô địch U-17 thế giới, ghi được 3 bàn ở vòng bảng nhưng U-17 Anh bị loại ở tứ kết.

Moses sau đó tiếp tục được gọi vào đội tuyển U-19 Anh, tham dự Giải vô địch U-19 châu Âu nhưng U-19 Anh bị loại ngay vòng bảng. Đầu mùa giải 2010-2011, anh được gọi vào đội tuyển U-21 Anh và có trận đầu tiên gặp U-21 Uzbekistan.[66]

Nigeria

Moses được gọi vào Nigeria cho trận đấu với Guatemala vào tháng 2 năm 2011, nhưng trận giao hữu này đã bị hoãn.[67] 1 tháng sau, anh lại được triệu tập cho các trận đấu với Ethiopia và Kenya.[68] Tuy nhiên, anh không được thi đấu do việc đăng ký đổi quốc tịch của anh với FIFA chưa hoàn tất. Phải đến ngày 1 tháng 11 năm 2011, FIFA chính thức cho Moses và Shola Ameobi khoác áo Nigeria.[69] Anh có trận đấu đầu tiên cho Nigeria vào ngày 29 tháng 2 năm 2012 trong trận gặp Rwanda.

Ngày 13 tháng 10 năm 2012, anh có bàn thắng đầu tiên cho Nigeria với một cú đúp trong chiến thắng 6-1 trước Liberia và đưa đội bóng chính thức giành vé tham dự Cúp bóng đá châu Phi 2013 (CAN 2013).[70]

Moses được triệu tập vào danh sách đội tuyển Nigeria tham dự CAN 2013, giải đấu chính thức đầu tiên của anh trong màu áo đội tuyển quốc gia Nigeria.[71] Ngày 29 tháng 1, trong trận đấu cuối cùng của vòng bảng với Ethiopia, anh đã lập cú đúp đều từ chấm phạt đền giúp Nigeria lọt vào vòng sau ở vị trí nhì bảng.[72] Chung cuộc, Nigeria đã giành chức vô địch châu lục lần đầu tiên kể từ năm 1994 và Moses cũng giành được danh hiệu Cầu thủ thi đấu Fair Play nhất giải đấu.[73]

Ngày 16 tháng 11, Moses ghi bàn thắng mở tỉ số trong chiến thắng 2-0 trước Ethiopia tại lượt về vòng loại World Cup khu vực châu Phi lượt đấu cuối cùng, chính thức đưa Nigeria tham dự World Cup 2014 tại Brasil.[74] Thành tích xuất sắc trong màu áo đội tuyển và câu lạc bộ trong năm 2013 đã giúp anh giành danh hiệu Cầu thủ Nigeria xuất sắc nhất năm vào ngày 27 tháng 11. Sau khi nhận giải thưởng, Moses đã chia sẻ trên Twitter rằng: "Đó là giấc mơ trở thành sự thật khi chơi cho đất nước của mình, tôi rất cảm ơn các bạn."[75]

Tháng 6 năm 2014, Moses được triệu tập vào đội hình đội tuyển Nigeria tham dự World Cup 2014 tại Brasil.[76] Tại giải đấu này, anh được ra sân trong trận đấu vòng bảng với Iran và trận thua 2-0 trước Pháp ở vòng 1/16.

Moses tiếp tục có cơ hội tham dự World Cup 2018 tại Nga.[77] Anh ra sân trong cả ba trận vòng bảng bảng D, có một đường chuyền thành bàn trong trận thắng 2-0 trước Iceland[78] và ghi được một bàn thắng từ chấm phạt đền trong trận thua 1-2 trước Argentina.[79] Chung cuộc đội tuyển Nigeria rời giải với vị trí thứ 3 bảng đấu.

Sau giải đấu đó, Victor Moses tuyên bố chia tay đội tuyển Nigeria sau 6 năm gắn bó để tập trung cho sự nghiệp câu lạc bộ, tổng cộng anh đã thi đấu 37 trận và ghi được 12 bàn thắng.[80]